package com.company.test24;

/**
 * Created by Administrator on 2016.10.18.
 */
public class QuickSort {
    public static void quickSort(int[] list){
        quickSort(list,0,list.length-1);
    }

    private static void quickSort(int[] list,int first,int last){
        if(last>first){
            int p=partition(list,first,last);
            quickSort(list,first,p-1);
            quickSort(list,p+1,last);
        }
    }

    private static int partition(int[] list,int first,int last){
        int pivor=list[first];
        int low=first+1;
        int high=last;

        while (high>low){
            while (low<=high&&list[low]<=pivor){
                low++;
            }
            while (high>=low&&list[high]>pivor){
                high--;
            }

            if(high>low){
                int t=list[low];
                list[low]=list[high];
                list[high]=t;
            }
        }



        if(pivor>list[high]){
            list[first]=list[high];
            list[high]=pivor;
            return high;
        }else {
            return first;
        }
    }

    public static void main(String[] args) {
        int[] list=new int[6];
        list[0]=2534;
        list[1]=3512;
        list[2]=28351;
        list[3]=6618;
        list[4]=1805;
        list[5]=12884;

        quickSort(list);

        for(int i=0;i<6;i++){
            System.out.println(list[i]);
        }
    }
}